import java.util.ArrayList;
import java.util.List;

public class Solution204 {
    public int countPrimes(int n) {
        boolean[] isPrime = new boolean[n];
        /*int res = 0;
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                res++;
                if (i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = true;
                    }
                }
            }
        }
        return res;*/
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < n; i++) {
            if (!isPrime[i]) {
                primes.add(i);
            }
            int j = 0;
            while (j < primes.size()) {
                int prime = primes.get(j);
                if (i * prime >= n) {
                    break;
                }
                isPrime[i * prime] = true;
                if (i % prime == 0) {
                    break;
                }
                j++;
            }
        }
        return primes.size();
    }
}
